前言
关于 数据结构与算法 知识体系的总结。
常用的数据结构
- 数组 array
- 链表 list
- 栈 stack
- 队列 queue
- 树 tree
- 哈希表（散列表） hash
- 堆 heap
- 图 graph
数组
特点
- 元素在内存中连续存放，每个元素占用的相同的空间。
- 可以通过下标迅速访问数组元素。$O(1)$
- 插入和删除效率低（需要整体移动腾出空间或者删除空间）。$O(n)$
- 需要预留空间，在定义的时候就定义好大小并申请内存空间。
- 难以扩展。
STL vector
STL 中的 vector 是封装了动态大小数组的顺序存储容器，它与数组有着非常多的相似之处，可以直接进行随机访问，与数组不同的是，vector 可以动态地增加大小，可以在末尾增加/删除元素。并且 vector 拥有迭代器，也可以通过迭代器进行访问。
链表
特点
- 元素在内存中非连续存放，依靠指针进行连接。
- 每个元素存储占用的空间比数组更大（需要存储下一个位置的指针，双向链表还需存储上一个位置的指针）
- 随机访问的效率低，需要按照链表的顺序遍历。$O(n)$
- 插入和删除效率高，在相应结点修改指针进行连接。$O(1)$
- 无需事先知道数据大小，可以在插入结点的时候再申请空间，内存利用率高。
- 易于动态扩展。
STL list
STL 中的 list 就是封装好的双向链表容器。
栈
特点
- 栈是一种特殊的线性表。
- 按照先进后出（FILO）的规则存储数据。
- 只能在一端（栈顶）执行插入和删除操作。
STL stack
STL 中的 stack 就是封装好的栈容器。
队列
特点
- 队列是一种特殊的线性表。
- 按照先进先出（FIFO）的规则存储数据。
- 可以在队头执行删除操作，在队尾执行插入操作。
STL queue
STL 中的 queue 就是封装好的队列容器。
STL deque
STL 中的 deque 是封装好的双端队列。可以从队列的两端插入和删除元素。与 vector 类似，支持随机访问和快速插入删除。
树
特点
- 由有限结点组成的具有层次关系的一个集合。
- 每个节点有 0 个或多个子节点。
- 没有父节点的节点称为根。
- 每一个非根节点有且仅有一个父节点。
- 除了根节点外，每个子节点可以分为多个不相交的子树。
二叉树
- 每个节点至多含有两个子树（分别称为左子树、右子树）。
完全二叉树
- 设二叉树的深度为 h。
- 除第 h 层外，其它各层 (1～(h-1)层) 的结点数都达到最大个数。
- 第 h 层所有的结点都连续集中在最左边。
满二叉树
- 二叉树的所有层结点数都达到最大个数。
二叉查找树
- 也成为二叉搜索树、有序二叉树。
- 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值。
- 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值。
- 任意节点的左、右子树也分别为二叉查找树。
- 没有键值相等的节点。
平衡二叉树
- 当且仅当任何节点的两棵子树的高度差不大于 1 的二叉树
- 典型的平衡二叉树：AVL 树（自平衡二叉搜索树）
红黑树
- 红黑树是一种弱平衡二叉树，旋转次数更少。
- 每个结点要么是红的要么是黑的。（红或黑）
- 根结点是黑的。（根黑）
- 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。（叶黑）
- 如果一个结点是红的，那么它的两个儿子都是黑的。（红子黑）
- 对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。（路径下黑相同）
- 红黑树的调整操作方式有旋转和变色两种。
哈夫曼树
- 一种带权路径长度最短的二叉树。
- 也称为最优二叉树。
多路查找树
B/B+ 树
- B/B+树是为了磁盘或其它存储设备而设计的一种平衡多路查找树。
- 在大规模的数据存储中，二叉查找树会由于深度过大而造成磁盘 I/O 读写频繁，因而造成效率低下。
- 在相同的的节点的情况下,一颗B/B+树的高度远远小于红黑树的高度。
STL set 和 map
set
- set 表示的是一个集合。
- set 中的元素都是唯一的。
- set 中的元素在插入的时候就会进行排序（默认升序）。
- set 中的元素的值并不能直接被改变，需要使用迭代器。
- set 的底层实现是红黑树。
由于以上特点的存在，set 的插入删除和查找的效率是 $O(\log n)$ 的。set 中的元素可以使用迭代器 iterator 进行访问。
multiset
与 set 的功能类似，不同的是允许插入重复的值。
map
- map 表示的是一个映射集合，保存的是 key-value 对。
- map 中的关键字（key）是唯一的。
- map 中的元素在插入的时候就会根据 key 进行排序（默认升序）。
- map 中的元素的值并不能直接被改变，需要使用迭代器。
- map 的底层实现是红黑树。
map 与 set 非常相似，只是存储的是一个数据对，其中一个是关键字，作为标识，而关键字对应的值则只跟随关键字，没有类型、大小等等限制。可以使用 map 的迭代器的成员变量 first 和 second 来访问关键字和值，也可以直接使用关键字作为下标进行访问，得到的是对应的值。
multimap
与 map 的功能类似，不同的是允许插入重复的关键字。相应的，multimap 就不再支持通过关键字作为下标进行访问。
哈希表
特点
- 根据关键码值(Key value)而直接进行访问。
- 通过哈希函数把关键码值映射到表中一个位置。
- 插入删除和查找的复杂度都是 $O(1)$ 。
哈希函数
一个好的哈希表离不开好的哈希函数。好的哈希函数计算快并且冲突少，才能真正达到 $O(1)$ 的复杂度。哈希函数设计的考虑因素有以下几点
- 关键字的长度和表的长度
- 计算散列地址所需要的时间较小（也即哈希函数不能太复杂）
- 关键字分布是否均匀，是否有规律可循
- 在满足以上条件的情况下尽量减少冲突
哈希冲突的解决办法
经过哈希函数处理后仍然有不同的数据对应相同的值，也即不同的关键字映射到相同的位置上，这时候就产生了哈希冲突。我们一般有开放定址法、链地址法、公共溢出区法、再哈希法。下面中的 $\alpha$ 表示装填因子，装填因子=数据总数/哈希表长。
1.开放定址法
开放其他关键字对应的位置给产生冲突的关键字放置。
- 线性探测再散列：发生哈希冲突时在原来值的基础上往后加一个单位，直至不发生哈希冲突。查找效率 $S_{nl}\approx\frac{1}{2}(1+\frac{1}{1-\alpha})$ 。
- 平方探测再散列：发生哈希冲突时在原来值的基础上先加1的平方个单位，若仍然存在则减1的平方个单位。随之是2的平方，3的平方等等。直至不发生哈希冲突。
- 随机探测再散列：发生哈希冲突时通过伪随机函数随机生成一个数，在原来值的基础上加上随机数，直至不发生哈希冲突。查找效率 $S_{nr}\approx-\frac{1}{\alpha}\ln(1-\alpha)$ 。
2.链地址法
产生哈希冲突后在存储数据后面加一个指针，指向后面冲突的数据。查找效率 $S_{nc}\approx 1+\frac{\alpha}{2}$ 。
- 处理冲突简单，无堆积现象（非同义词不会产生冲突），因此平均查找长度较短。
- 由于链表上的结点空间是动态申请的，因此更适合难以事先知道表长的情况。
- 开发定址法为了减少冲突，要求装填因子较小（也不能超过1），浪费的空间也比较多。而链地址法中装填因子甚至可以超过1，当然，过长的链条也会使哈希表退化成为 $O(n)$ 的复杂度。
- 使用链地址法构造的哈希表删除结点更加简单，直接删去链表上相应结点即可。
3.公共溢出区法
建立公共溢出区存储所有哈希冲突的数据。
4.再哈希法
对于冲突的哈希值再次进行哈希处理，直至没有哈希冲突。
STL unordered_set 和 unordered_map
unordered_set
- unordered_set 表示的是无序集合。
- unordered_set 的其他性质与 set 类似。
- unordered_set 的底层实现是哈希表。
unordered_map
- unordered_map 表示的是无序映射集合。
- unordered_map 的其他性质与 map 类似。
- unordered_map 的底层实现是哈希表。
堆
特点
- 堆其实看做是用数组实现的完全二叉树（按照层序遍历存储）。
- 最大堆的节点的值总是不大于其父节点的值。
- 最小堆的节点的值总是不大于其父节点的值。
- 根结点下标从 0 开始
- 左子节点的下标为 2 * i + 1
- 右子节点的下标为 2 * i + 2
用途
- 快速找出集合中的最大值或最小值
- 构造优先队列
- 堆排序
堆和二叉搜索树的区别
- 节点顺序不同。堆中的根结点是最大值或者最小值，而二叉搜索树的根结点是中间值。
- 堆的内存占用更小。二叉树需要指针指向子节点，而堆使用数组存储。
- 堆的平衡更简单。二叉树必须在平衡的情况下才能保证大部分操作是 $O(\log n)$ 的，而堆不需要整棵树都有序，可以保证所有的操作都具有 $O(\log n)$ 的性能。
- 二叉树的搜索更快。二叉搜索树建立之后，只要是平衡的，搜索的性能就能够达到 $O(\log n)$，而堆主要处理的是最大值或最小值，快速地进行相关的插入和删除操作，搜索性能会比较差。
调整堆
下面是调整堆的代码。我们在加入一个结点的时候，需要对堆进行调整使堆依然保持特性。根结点下标为 begin，堆尾下标（也即堆的大小）为 k。需要保证的是除了刚加入的根结点，其叶子结点都已经满足堆的特性。一次调整的时间复杂度为 $O(\log n)$。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16void adjustMinHeap(vector<int>& nums, int begin, int k){
while(2 * begin + 1 < k){
int minChild = 2 * begin + 1; // 赋为左孩子
// 若右孩子更小则赋为右孩子
if(minChild + 1 < k && nums[minChild] > nums[minChild + 1]){
minChild = minChild + 1;
}
// 孩子比双亲小则交换
if(nums[begin] > nums[minChild]){
swap(nums[begin], nums[minChild]);
// 需要重新调整被破坏的孩子
begin = minChild;
}
else break;
}
}
建立堆
调整堆的代码就是上面所给出的代码。我们只需要自底向上将每个子树都调整到符合堆特性即可，这样就完成了一个堆的建立。这个操作的时间复杂度是 $O(n)$。
1 | for(int begin = k / 2 - 1; begin >= 0; begin--){ |
STL 中的堆
在 STL 的头文件 algorithm 中含有关于堆的代码。当然实际应用的时候通常会要求我们自己实现堆的操作。
STL 中的堆支持以下的基本操作:1
2
3
4make_heap(first, last, comp); //建立一个空堆；
push_heap(first, last, comp); //向堆中插入一个新元素；
top_heap(first, last, comp); //获取当前堆顶元素的值；
sort_heap(first, last, comp); //对当前堆进行排序；
图
特点
- 由顶点和连接顶点的边构成的离散结构。
- 有向图的边具有方向性。
- 加权图的边具有权重。
- 完全图的每两个顶点之间都有边。
- 树是一种特殊的有向图。
图的表示
- 邻接矩阵：一个拥有 V 个顶点的图使用一个 V * V 的矩阵表示，行和列都表示顶点，由两个顶点所决定的矩阵对应元素表示这里两个顶点是否相连、如果相连这个值表示的是相连边的权重。
- 邻接链表：一个拥有 V 个顶点的图使用一个大小为 V 的线性表和一些链表表示，每个顶点连接的链表表示与其有邻接关系的顶点。如果对查询的要求较高的话，链表也可以换成其他高效的查找结构（如哈希表）。
图的遍历
- 深度优先搜索（DFS）
- 广度优先搜索（BFS）
- 拓扑排序：给定一副有向图，将所有的顶点排序，使得所有的有向边均从排在前面的顶点指向排在后面的顶点。（如果一个有向图有环则没有拓扑排序）
最小生成树
- 图的生成树：是它的一棵含有其他所有顶点的无环连通子图。
- 加权无向图的最小生成树（MST）：是它的一棵所有边的权值之和最小的生成树。
- Prime 算法（加点法）：先选择一个顶点，并不断将下一条连接树中的顶点与不在树中的顶点且权重最小的边加入树中。（优先队列）
- Kruskal 算法（加边法）：按照边的权重顺序不断将最小的边加入到生成树中，不能和已有的边产生环。（优先队列和并查集）
最短路径
- 加权有向图的最短路径问题：找到从一个顶点到达另一个顶点的成本（权重和）最小的路径。
- DFS 和 BFS（单源最短路径）
- Floyd 算法（允许负权边（但不能在环路上），多源最短路径，动态规划思想）：最开始只允许经过1号顶点进行中转，接下来只允许经过1和2号顶点进行中转，直到允许经过 1~n 号所有顶点进行中转，求任意两点之间的最短路程。（$O(v^3)$ 时间复杂度和 $O(v^2)$ 空间复杂度）
- Dijkstra 算法（不允许负权边，单源最短路径，贪心法思想）：每次找到离源点最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。（$O(v^2)$ 的时间复杂度，如果边数远小于 $v^2$ 则可以使用堆优化到 $O(e\log v)$ 的时间复杂度）
- Bellman-Ford 算法（允许负权边，单源最短路径）：对所有的边进行 n-1 轮松弛操作，得到从某一点出发到其他点的最短路径，同时可以判断是否存在负权环。（时间复杂度 $O(ve)$，空间复杂度 $O(e)$）